﻿using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    public static class DecimalArithmetic
    {
        public static void Add(Int32[] sum, Int32[] addend)
        {
            var d = sum.Length - 1;
            var carry = 0;

            while (d >= 0)
            {
                carry = Math.DivRem(carry + (sum[d] + addend[d]), 10, out sum[d]);
                d -= 1;
            }
        }

        public static Stack<Int32> DecimalDigits(this Int32 n)
        {
            var stack = new Stack<Int32>();

            while (n > 0)
            {
                Int32 remainder;

                n = Math.DivRem(n, 10, out remainder);

                stack.Push(remainder);
            }

            return stack;
        }
        
        public static Stack<Int64> DecimalDigits(this Int64 n)
        {
            var stack = new Stack<Int64>();

            while (n > 0)
            {
                Int64 remainder;

                n = Math.DivRem(n, 10, out remainder);

                stack.Push(remainder);
            }

            return stack;
        }

        public static Int32[] ExponentiateBySquaring(Int32[] x, Int32 n)
        {
            var y = new Int32[x.Length];
            y[y.Length - 1] = 1;

            var z = (Int32[])x.Clone();

            while (n > 0)
            {
                if ((n % 2) == 1)
                {
                    y = LongMultiplication(y, z);
                }

                z = LongMultiplication(z, z);
                n /= 2;
            }

            return y;
        }

        public static Int32[] LongMultiplication(Int32[] multiplicand, Int32[] multiplier)
        {
            var digitsCand = SignificantDigits(multiplicand);
            var digitsEr = SignificantDigits(multiplier);

            if (digitsCand < digitsEr)
            {
                Swap(ref multiplicand, ref multiplier);
                Swap(ref digitsCand, ref digitsEr);
            }

            var product = new Int32[multiplicand.Length];

            for (int i = 0; i < digitsEr; i++)
            {
                var term = LongMultiplication(multiplicand, i, multiplier[multiplier.Length - i - 1]);
                Add(product, term);
            }

            return product;
        }

        private static Int32[] LongMultiplication(Int32[] multiplicand, Int32 tenPower, Int32 multiplier)
        {
            var product = new Int32[multiplicand.Length];

            if (multiplier > 0)
            {
                var src = multiplicand.Length;
                var dest = multiplicand.Length - tenPower;

                var carry = 0;

                while ((--dest >= 0) && (--src >= 0))
                {
                    carry = Math.DivRem(carry + (multiplicand[src] * multiplier), 10, out product[dest]);
                }
            }

            return product;
        }

        private static void Swap<T>(ref T a, ref T b)
        {
            var tmp = a;
            a = b;
            b = tmp;
        }

        private static Int32 SignificantDigits(Int32[] digits)
        {
            var result = digits.Length;
            var i = 0;

            while ((result > 0) && (digits[i] == 0))
            {
                result--;
                i++;
            }

            return result;
        }
    }
}
